A conventional objective of frequency planning in a wireless network is maximizing the network throughput by reducing inter-cell interference. However, the conventional objective of maximizing the network throughput by reducing inter-cell interference is not directly applicable to wireless local area networks (WLANs), e.g., IEEE 802.11 WLANs, because WLANs inherently provide unfair service. For example, users nearer an access point (AP) in conventional WLANs receive significantly higher throughput than users farther from the AP. The phenomenon of unfair service is greatly aggravated in the presence of interference from adjacent cells, which may cause users which are farther from the AP to suffer starvation while users which are nearer to the AP monopolize the resources. Users nearer the AP enjoy higher data transmission rates and users farther from the AP have to use lower data rates. As a result, frequency planning resulting in higher interference may increase the overall network throughput by starving users farther from the AP and servicing only users nearer the AP because servicing only users nearer the AP maximizes the network throughput.
With the rapid growth in the deployment of IEEE 802.11 WLANs, performance enhancement of WLAN networks has been a research issue. Wireless channel allocation to the APs is one issue. Channel allocation, also known as frequency planning, has a relatively great deal of influence on the system performance of wireless networks. In particular, channel allocation is well studied in the context of cellular wireless telephony. Conventional channel allocation methods are more suited to the cellular telephony scenario, rather than to WLANs. Conventional channel allocation techniques that are applicable to cellular telephony may not be directly applied to WLANs due to technology differences.
For example, a number of non-overlapping channels available for the two most widely deployed WLAN standards, i.e., IEEE 802.11b/g, is very limited. In the United States, among 11 available channels, only three are mutually non-interfering. This limited number of channels means that for reasonably sized networks, conventional graph coloring techniques may not provide channel allocations where all of the cells are free from interference by neighboring cells. Further, the spectrum for 802.11 networks is unlicensed and is therefore subject to interference from external sources. In WLANs, each station performs carrier sensing and sends a packet, only if the channel is idle for a certain duration. Consequently, even weak but long-lasting interference may significantly hinder the performance of WLANs. However, for cellular systems where resources are allocated to each mobile via some sort of reservation scheme, weak but long-lasting interference may not significantly hinder performance.